import java.util.HashMap;

// 利用先序与中序遍历序列构造二叉树
// 测试链接 : https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
public class PreorderInorderBuildBinaryTree {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {
        }
        TreeNode(int val) {
            this.val = val;
        }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder == null || inorder == null || preorder.length != inorder.length) {
            return null;
        }
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i = 0; i < inorder.length; ++i){
            map.put(inorder[i],i);
        }

        return func(preorder,0,preorder.length-1,inorder,0,inorder.length-1,map);
    }

    public TreeNode func(int[] preorder,int l1,int r1, int[] inorder,int l2,int r2, HashMap<Integer,Integer> map){
          if(l1 > r2){
              return null;
          }
          int key = preorder[l1];
          TreeNode node = new TreeNode(key);
          if (l1 == r1){
              return node;
          }
          int pos = map.get(key);
          node.left = func(preorder,l1+1,l1+pos-l2,inorder,l2,pos-1,map);
          node.right = func(preorder,l1+pos-l2+1,r1,inorder,pos+1,r2,map);

          return node;
    }

}
